package algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/***
 * 感觉没想法就很难，完全没想到倒着写的写法。
 * 单调栈有个好处，例如从右往左单调递减的曲线↙，他可以突然发现一个突然升高，构成一个V字结构，
 * 之后退栈行成全新的右到左的曲线↙，如果后面是新的元素可以继续构成从右到左的下降曲线↙，
 * 如果这个时候回过头想想刚刚的V字结构，这个时候算上新加的元素，刚好构成一个N字结构，
 * 这个时候只要判断这个N的左边是否是132就行了，也就是判断新点的原V结构的最低点的大小比
 */
//[3, 1, 4, 2]
//[1, 2, 3, 4]
public class LeetCode_456_find132pattern {
    public boolean find132pattern(int[] nums) {
        int length = nums.length;
        if (length < 3) return false;
        Deque<Integer> stack = new LinkedList<Integer>();
        int minValue = Integer.MIN_VALUE;
        for (int i = length - 1; i >= 0; i--) {
            if (nums[i] < minValue) {
                return true;
            }
            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                minValue = stack.pop();
            }
            stack.push(nums[i]);
        }
        return false;
    }

    public static void main(String[] args) {

    }
}
